package cn.nky.datastructures;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //先创建几个节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        HeroNode hero5 = new HeroNode(5,"林冲1","豹子头1");
        HeroNode hero6 = new HeroNode(6,"林冲2","豹子头2");
        HeroNode hero8 = new HeroNode(7,"林冲2","豹子头2");
        HeroNode hero7 = new HeroNode(5,"林冲2","豹子头2");

        SingleLinkedList list = new SingleLinkedList();
        SingleLinkedList list2 = new SingleLinkedList();

       /* list.add(hero1);
        list.add(hero2);
        list.add(hero3);
        list.add(hero4);*/

        list.addOrder(hero1);
        list.addOrder(hero4);
        list.addOrder(hero3);
        list.addOrder(hero2);
        list.addOrder(hero7);

        list2.addOrder(hero5);
        list2.addOrder(hero6);
        list2.addOrder(hero8);
        //list.addOrder(hero2);

        //显示
        System.out.println("链表1：");
        list.list();
        System.out.println("链表2：");
        list2.list();

        System.out.println("合并链表：");
        newHead(list.getHead(),list2.getHead());
        list.list();
        //测试逆序打印单链表
       /* System.out.println("逆序打印后的结果：");
        reversePrint(list.getHead());*/


        //测试链表反转
       /* System.out.println("反转后的链表");

        reverseNode(list.getHead());
        list.list();*/

      /*  HeroNode hero5 = new HeroNode(4,"小宋","及时雨~~");
        list.update(hero5);
        //修改后显示
        System.out.println("修改后的链表");
        list.list();

        //删除一个节点
        //list.delete(2);
        list.delete(4);

        //删除后遍历
        System.out.println("删除后的节点");
        list.list();
        //测试获取节点方法
        System.out.println("链表节点的个数为：" + getLength(list.getHead()));*/
        //测试获取倒数第k个节点
        /*int index = 2;
        System.out.println("倒数第" + index + "个节点是" + findLastIndexNode(list.getHead(),index));*/

    }
    //获取到单链表的节点个数，如果是头节点的话，要求不统计头节点
    public static int getLength(HeroNode head){
        if(head.next == null){
            return 0;
        }
        int length = 0;
        //定义辅助节点
        HeroNode cur = head;
        while(true){
            if(cur.next == null){
                break;
            }
            length++;
            cur = cur.next;
        }
        return length;
    }

    //查找链表倒数第K个节点（新浪面试）
    //1.编写一个方法接收 head节点，同时接收index
    //2.index表示倒数第index个节点
    //3，将链表从头到尾遍历一遍，得到链表的总长度 getLength
    //4,得到size后，从链表的第一个开始遍历（size-index)个
    //如果找到则返回该节点，否则返回null
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if(head.next == null){
            return null;
        }
        //获取链表的大小
        int size = getLength(head);
        //数据校验
        if(index <=0 || index > size){
            return null;
        }
        //定义一个辅助变量
        HeroNode temp = head.next;//指向第一个节点
        for (int i = 0; i < size-index; i++) {
          temp = temp.next;
        }
        return temp;
    }
    //单链表反转
    //1.先定义一个新节点
    //2.从头到尾遍历一遍，每遍历一个节点，将其取出，并放在新的链表最前端
    public static void reverseNode(HeroNode head){
        if(head.next == null || head.next.next == null){
            return;
        }
        //定义一个辅助的变量
        HeroNode temp = head.next;//第一个节点
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","");
        //        //遍历原来的链表
        //难点******
        while (temp!=null){
            next = temp.next;//先指向下一个节点
            //将temp的下一个节点指向新的链表的最前端
            temp.next = reverseHead.next;
            //将temp连接到新的链表上
            reverseHead.next = temp;
            //后移
            temp = next;
        }
        //将head.next 指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }
    //从尾到头打印链表
    //思路：要求，逆序打印链表
    //方式1：先将单链表进行反转操作，然后遍历。问题：会破坏原来的单链表的结构，不建议
    //方式2：可以利用栈，将各个节点压入stack中，然后利用栈的先进后出的特点就实现逆序打印的效果
    //采用方式2
    public static void reversePrint(HeroNode head){
        if(head.next == null){
           return;
        }
        //创建一个栈，将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode temp = head.next;
        while (temp != null){
            stack.push(temp);
            //将temp后移
            temp = temp.next;
        }
        //将栈中的数据打印
        while (stack.size()>0){
            //先进后出
            System.out.println(stack.pop());
        }
    }

    public static void newHead(HeroNode head1,HeroNode head2){
        //定义两个辅助变量
        HeroNode temp1 = head1.next;
        HeroNode temp2 = head2.next;
        //HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","");
        HeroNode head = reverseHead;
        while (temp1 !=null){
            //System.out.println("取出的节点:"+temp1);
            head.next= temp1;
            temp1 = temp1.next;
            if(head.next == null){
                break;
            }else{
                head = head.next;
            }
        }
        head1.next = reverseHead.next;
        //遍历已经拼接好的第一个链表
        for (int i = 0; i < getLength(head1); i++){
            for (int j = 0; j < getLength(temp2); j++) {
                //判断该节点是否存在
               /*if(head1.next.no == temp2.no){
                    System.out.printf("节点%d已经存在\n",temp2.no);
                    break;
                }*/
                //如果该节点大于，则在后面插入
                if(temp2.no > head1.next.no){
                    head1.next = temp2;
                }
                temp2 = temp2.next;
            }
            head1 = head1.next;
        }
        /*while (temp2 !=null){
            //System.out.println("取出的节点:"+temp1);
            head.next= temp2;
            temp2 = temp2.next;
            if(head.next == null){
                break;
            }else{
                head = head.next;
            }
        }*/
       head1.next = reverseHead.next;
    }
}



//定义SingleLinkedList管理我们的英雄
class SingleLinkedList{
    //先初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead(){
        return head;
    }

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2.将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp
        HeroNode temp = head.next;
        //遍历链表，找到最后
        while(true){
            //找到链表的最后
            if (temp.next == null){
                //找到最后的条件为next=null
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next指向 新的节点
        temp.next = heroNode;
    }
    //排名形式添加节点，不能重复
    public void addOrder(HeroNode heroNode){
        //因为head节点不能动，因此我们需要一个辅助变量temp来帮助找到添加的位置
        //因为是单链表，因此找的temp是位于 添加位置的前一个节点，否者插入不了
        HeroNode temp = head;
        boolean flag = false;//标识添加的标号是否存在，默认为false
        while (true){
            if(temp.next==null){//说明temp已经在链表的最后
                break;
            }
            if(temp.next.no > heroNode.no){//位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no == heroNode.no){
                //说明编号存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag){
            //不能添加，说明编号存在
            System.out.printf("准备加入的%d已经存在\n",heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改英雄信息
    public void update(HeroNode newHeroNode){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //根据no编号，找到需要修改的节点，头节点不能动，需要一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;

        while (true){
            if(temp == null){
                //到达链表尾部
                break;
            }
            if(temp.no == newHeroNode.no){
                //已近找到需要修改的节点
                System.out.println("找到的节点为"+temp);
                flag = true;
                break;
            }
            //将temp后移，不断的遍历
            temp = temp.next;
        }
        //根据返回的情况作出不同的操作
        if(flag){
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else{
            System.out.printf("没有找到 编号为%d的英雄\n",newHeroNode.no);
        }
    }
    //删除单个节点思路：
    //1.head不能动需要一个temp辅助节点,找到待删除节点的前一个节点
    //2.当找到需要删除的节点时temp.next = temp.next.next
    //3.被删除的节点将不会有其他的引用，会被垃圾回收机制回收

    //head不能动需要一个temp辅助节点
    public void delete(int no){
        //定义辅助变量
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.next == null){
                //遍历到最后的节点
                break;
            }
            if(temp.next.no == no){
                //找到该节点
                flag = true;
                break;
            }
            //temp后移
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }else{
            System.out.println("没有找到要删除的节点");
        }
    }
    //遍历节点
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        //因为头节点不能动，因此需要一个辅助变量来遍历
        while(true){
            //判断是否到两遍最后
            if(temp == null){
                break;
            }
            System.out.println(temp);
            //将temp后移
            temp = temp.next;
        }
    }
}

//定义HeroNode，每一个HeroNode对象就是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    //构造器
    public HeroNode(int no,String name,String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '}';
    }
}